import java.util.*;
public class test {
    // leetcode 1262.可被三整除的最大和
    // 1.贪心
    public int maxSumDivThree1(int[] nums) {
        // 用 v[0], v[1], v[2] 分别表示 a, b, c
        List<Integer>[] v = new List[3];
        for (int i = 0; i < 3; ++i) {
            v[i] = new ArrayList<>();
        }
        for (int x : nums) {
            v[x % 3].add(x);
        }
        Collections.sort(v[1], (a, b) -> b - a);
        Collections.sort(v[2], (a, b) -> b - a);
        int ans = 0;
        int len1 = v[1].size(), len2 = v[2].size();
        for (int cnt1 = len1 - 2; cnt1 <= len1; ++cnt1) {
            if (cnt1 >= 0) {
                for (int cnt2 = len2 - 2; cnt2 <= len2; ++cnt2) {
                    if (cnt2 >= 0 && (cnt1 - cnt2) % 3 == 0) {
                        ans = Math.max(ans, sum1(v[1], 0, cnt1) + sum1(v[2], 0, cnt2));
                    }
                }
            }
        }
        return ans + sum1(v[0], 0, v[0].size());
    }

    public int sum1(List<Integer> v, int start, int end) {
        int ret = 0;
        for (int i = start; i < end; ++i) {
            ret += v.get(i);
        }
        return ret;
    }

    // 2. 贪心 + 正难则反
    public int maxSumDivThree(int[] nums) {
        // 用 v[0], v[1], v[2] 分别表示 a, b, c
        List<Integer>[] v = new List[3];
        for (int i = 0; i < 3; ++i) {
            v[i] = new ArrayList<>();
        }
        int total = 0;
        // int total = Arrays.stream(nums).sum();
        for (int x : nums) {
            v[x % 3].add(x);
            total += x;
        }
        Collections.sort(v[1], (a, b) -> b - a);
        Collections.sort(v[2], (a, b) -> b - a);
        int remove = Integer.MAX_VALUE;
        int n1 = v[1].size(), n2 = v[2].size();
        if (total % 3 == 0) {
            remove = 0;
        } else if (total % 3 == 1) {
            if (n1 > 0) {
                remove = Math.min(remove, v[1].get(n1 - 1));
            }
            if (n2 > 1) {
                remove = Math.min(remove, v[2].get(n2 - 1) + v[2].get(n2 - 2));
            }
        } else {
            if (n1 > 1) {
                remove = Math.min(remove, v[1].get(n1 - 1) + v[1].get(n1 - 2));
            }
            if (n2 > 0) {
                remove = Math.min(remove, v[2].get(n2 - 1));
            }
        }
        return total - remove;
    }
}
